package leetCode.q92;

public class Me {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode phead = new ListNode(0, head);
        ListNode lwall = null;
        ListNode rwall = null;
        ListNode rrwall = null;
        ListNode node = phead;

        for (int i = 0; i <= right; i++) {
            if (i + 1 == left) {
                lwall = node;
            }
            if (i == right) {
                rwall = node.next;
                rrwall = node.next;
            }
            node = node.next;
        }

        /**
         * 从第一个结点开始，先存储后继，再把后继改为rwall，再换成存储的后继,再更新rwall
         */
        ListNode next;
        for (ListNode cur = lwall.next; ; ) {
            if (cur.next == rrwall) {
                next = cur.next;
                cur.next = rwall;
                lwall.next = cur;
                break;
            }

            next = cur.next;
            cur.next = rwall;

            rwall = cur;
            cur = next;
        }
        return phead.next;
    }
}